package Backtracking;
/*
 * 分割回文串
 */
import java.util.ArrayList;
import java.util.List;

public class lc131 {

    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(s, 0, new StringBuilder());
        return result;
    }
    public void backtracking(String s, int start, StringBuilder sb) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (check(sb)) {
                path.add(sb.toString());
                backtracking(s, i + 1, new StringBuilder());
                path.remove(path.size() - 1);
            }
        }

    }
    public boolean check(StringBuilder sb) {
        for (int i = 0; i < sb.length() / 2; i++) {
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) return false;
        }
        return true;
    }

}
